1. Field of the Invention
The present invention generally relates to data communications, and more specifically, relates to an apparatus and method for handling data packets.
2. Description of the Related Art
A local area network (LAN) is the most basic and simplest network that allows communication between a source computer and destination computer. The LAN is often diagramed as a cloud to which computers (also called end stations or end-nodes) that wish to communicate with one another are attached. At least one network element will connect with all of the end stations in the LAN. A single LAN, however, may be insufficient to meet the requirements of an organization that has many end stations because of the limited number of physical connections available to, and the limited message handling capability of, a single repeater.
The capability of computer networks, however, has been extended by connecting different sub-networks to form larger networks that contain thousands of end-stations communicating with each other. These LANs can in turn be connected to each other to create even larger enterprise networks, including wide area network (WAN) links.
To facilitate communication between subnets in a larger network, more complex electronic hardware and software have been proposed and are currently used in conventional networks. Also, new sets of rules for reliable and orderly communication among those end-stations have been defined by various standards based on the principle that the end-stations interconnected by suitable network elements define a network hierarchy, where end-stations within the same subnet have a common classification. A network is thus said to have a topology which defines the features and hierarchical position of nodes and end stations within the network.
The interconnection of end stations through packet switched networks has traditionally followed a peer-to-peer layered architectural abstract. In such a model, a given layer in a source computer communicates with the same layer of a pier end station (usually the destination) across the network. By attaching a header to the data unit received from a higher layer, a layer provides services to enable the operation of the layer above it. A received packet will typically have several headers that were added to the original payload by the different layers operating at the source.
There are several layer partition schemes in the prior art, such as the Arpanet and the Open Systems Interconnect (OSI) models. The seven layer OSI model used here to describe the invention is a convenient model for mapping the functionality and detailed implementations of other models. Aspects of the Arpanet, however, (now redefined by the Internet Engineering Task Force or IETF) will also be used in specific implementations of the invention to be discussed below.
The relevant layers for background purposes here are Layer 1 (physical), Layer-2 (data link), and Layer-3 (network), and to a limited extent Layer-4 (transport). A brief summary of the functions associated with these layers follows.
The physical layer transmits unstructured bits of information across a communication link. The physical layer concerns itself with such issues as the size and shape of connectors, conversion of bits to electrical signals, and bit-level synchronization. Layer-2 provides for transmission of frames of data and error detection. More importantly, the data link layer as referred to in this invention is typically designed to “bridge,” or carry a packet of information across a single hop, i.e., a hop being the journey taken by a packet in going from one node to another. By spending only minimal time processing a received packet before sending the packet to its next destination, the data link layer can forward a packet much faster than the layers above it, which are discussed next. The data link layer provides addressing that may be used to identify a source and a destination between any computers interconnected at or below the data link layer. Examples of Layer-2 bridging protocols include those defined in IEEE 802, such as CSMA/CD, token bus, and token ring (including Fiber Distributed Data Interface, or FDDI).
Similar to Layer-2, Layer-3 also includes the ability to provide addresses of computers that communicate with each other. The network layer, however, also works with topological information about the network hierarchy. The network layer may also be configured to “route” a packet from the source to a destination using the shortest path.
Finally, Layer-4, the transport layer, provides an application program such as an electronic mail program with a “port address” which the application can use to interface with Layer-3. A key difference between the transport layer and the lower layers is that a program on the source computer carries a conversation with a similar program on the destination computer, whereas in the lower layers, the protocols are between each computer and its immediate neighbors in the network, where the ultimate source and destination end-stations may be separated by a number of intermediate nodes. The transport layer can control congestion by simply dropping selected packets, which the source might recognize as a request to reduce the packet rate. Examples of Layer-4 and Layer-3 protocols include the Internet suite of protocols such as TCP (Transmission Control Protocol) and IP (Internet Protocol).
End-stations are the ultimate source and destination of a packet, whereas a node refers to an intermediate point between the end-stations. A node will typically include a network element which has the capability to receive and forward messages on a packet-by-packet basis.
Generally speaking, the larger and more complex networks typically rely on nodes that have higher layer (Layers 3 and 4) functionalities. A very large network consisting of several smaller sub-networks must typically use a Layer-3 network element known as a router which has knowledge of the topology of the sub-networks.
A router can form and store a topological map of the network around it based upon exchanging information with its neighbors. If a LAN is designed with Layer-3 addressing capability, then routers can be used to forward packets between LANs by taking advantage of the hierarchical routing information available from the end-stations. Once a table of end-station addresses and routes has been compiled by the router, packets received by the router can be forwarded after comparing the packet's Layer-3 destination address to an existing and matching entry in the memory.
In comparison to routers, bridges are network elements operating in the data link layer (Layer-2) rather than Layer-3. They have the ability to forward a packet based only on the Layer-2 address of the packet's destination, typically called the medium access control (MAC) address. Generally speaking, bridges do not modify the packets. Bridges forward packets in a flat network having no hierarchy without any cooperation by the end-stations.
Hybrid forms of network elements also exist, such as “brouters” and switches. A “brouter” is a router which can also perform as a bridge. The term switch refers to a network element which is capable of forwarding packets at high speed with functions implemented in hardwired logic as opposed to a general purpose processor executing instructions. Switches come in many types, operating at both Layer-2 and Layer-3.
A layer-2 switch (or bridge) determines the destination physical port based on layer-2 header (more specifically destination MAC address), and the packet stays intact (without any change) when it is forwarded out. A layer-3 router determines the destination physical port based on layer-3 header (destination IP address), and the layer-2 header (source MAC address and destination MAC address) of the packet is replaced with new values when it is forwarded out. A router can work as a bridge and router simultaneously. When a packet comes in, it performs a layer-2 switch or layer-3 routing based on its destination MAC address.
FIG. 1 illustrates an encapsulated data packet known in the prior art, specifically an encapsulated IP packet 100. The encapsulated IP packet 100 includes an IP packet encapsulated by a layer-2 MAC header 102. The IP packet includes a layer-3 IP header, a layer-3 header, and a payload, which is a data destined for a recipient identified by the layer-3 address and the layer-4 address.
FIG. 2 illustrates a prior art MAC header 200. The MAC header includes a destination MAC address, a source MAC address and an ether type information. If the ether type equals 0x0800 (hex), then the layer-3 address has an IPv4 format; if the ether type equals 0x86dd (hex), then the layer-3 address has an IPv6 format.
Generally each end-station on a network is assigned an address and the address most commonly used is IP address. Currently the most widely used addresses follow the IPv4 format. The IPv4 format uses 32-bit addresses, limiting it to 4,294,967,296 unique addresses, many of which are reserved for special purposes such as local networks or multicast addresses, reducing the number of addresses that can be allocated as public Internet addresses. A prior art header for the IPv4 format is illustrated in FIG. 3.
FIG. 4 illustrates a prior art IPv6 protocol. IPv6 is a new protocol meant to replace the existing IPv4 format, which is the major layer-3 protocol for the current Internet. Since the installed base of the IPv4 format is huge, the IPv6 format is slowly becoming used. There will be some transitions before IPv6 is deployed all over the world. It is possible that a private LAN is using the IPv6 format, but the ISP is using the IPv4 format. I such case, the IPv6 packet can be carried within an IPv4 packet via a tunnel set up by the gateway as illustrated by the prior art data packet in FIG. 5. Another scenario is that an IPv6 host wants to talk to an IPv4 host through an IPv4 network. In this case, the IPv6 header will be translated into an IPv4 header by the gateway in order for the two parties to communicate successfully. Consequently, the IPv6/IPv4 tunnel and translation are needed in current and future gateways.
Because of the scarcity of the IPv4 address space caused by reserving IPv4 format addresses to private networks or multicast addresses, it is very common for many computers inside a private network, such as a home or office, to have internal private network addresses. When the internal computers access someone outside over the Internet, the private network address is translated into a public network address, such as an IP address. Network Address/Port Translation (NAPT) is a technique for many hosts to share fewer public IP addresses. Because many hosts can share one single IP address, the layer-4 port number is used to distinguish an actual internal host. It is heavily used in a gateway application. A gateway is a device sitting between a private network and a wide area network, e.g. the Internet. When a packet comes in from a private LAN port of a gateway, the gateway determines the destination physical port based on the packet's destination network address, and then applies NAPT to generate a new source network address and port number. When a packet comes in from a WAN port of the gateway, the gateway first applies NAPT to generate a new destination network address and port number, and then determines a destination physical port number.
A network address may have different format depending on the protocol used by the network and it may need to be translated when a packet moves from one network to another. Point-to-Point Protocol (PPP) over Ethernet (PPPoE) is a protocol commonly used between an Internet Service Provider and its end users. The prior art PPPoE packet format and the PPPoE header are shown in FIG. 6. PPPoE is not generally used inside a home/office network; therefore, a gateway may need to perform a PPPoE packet encapsulation/decapsulation if necessary. Other commonly used protocols are transfer control protocol (TCP) and user datagram protocol (UDP). Both UDP and TCP are layer-4 protocols and their prior art header information are shown in FIG. 7 and FIG. 8 respectively.
Another issue when dealing with interfacing a private network and a public network is the Quality of Service (QoS) issue for certain real time applications. Under QoS guarantee, the packets belonging to real time applications, such as video and audio, should be transmitted as soon as possible no matter if the network is congested or not. To provide QoS guarantee, a gateway must be able to classify packets into difference classes so that important packets will not be disturbed by non important packets, and there must be some scheduler to select a packet from different classes to serve.
In summary, a gateway needs to check layer-2, layer-3, and layer-4 headers in a data packet in order to determine a destination physical port through which to forward the data packet, and when the data packet is forwarded out, the layer-2, layer-3 and layer-4 headers of the data packet will be replaced with new header information. While the incoming header information is checked and new header information is generated, the gateway must also be able to provide the QoS guarantee. Therefore, it is desirous to have an apparatus and method that handles incoming data packets in a fast and efficient way, and at the same time providing the QoS guarantee and it is to such apparatus and method the present invention is primarily directed.